package com.example.algorithm.sort;

// 学习顺序：第三
// 从前往后，把每个数往前面合适的地方插入.

// 插入排序的平均时间复杂度也是 O(n^2)，
// 但在某些特定情况下（例如，数组已经几乎有序），插入排序的时间复杂度可能会接近 O(n)。也就是相比冒泡和选择，它已经有些优化了。
public class InsertionSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 8, 4, 2};

        System.out.println("排序前的数组：");
        printArray(array);

        insertionSort(array);

        System.out.println("\n排序后的数组：");
        printArray(array);
    }

    // 插入排序方法
    // 结合图形理解一次之后，多写几遍记住。因为仅仅基于理解的话，不自己实际动手写的话，应该会遗漏很多细节。
    public static void insertionSort(int[] array) {
        int n = array.length; // 5
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1; // 从i自己的位置开始，然后它与自己左边的元素依次比较。并不断往前。所以，最开始j的初始值是i-1。
            // 为什么冒泡循环、选择循环，内层都是用for，但是这里是用while呢？因为我们不知道具体的循环次数。这也是插入排序相比冒泡排序、选择排序的优化之处，就是，冒泡排序和插入排序，即使在数据基本本身基本上算是有序的情况下，它的循环次数仍然是固定内外循环那么多次，而插入排序呢，在数组本身基本有序的情况下，循环次数是接近n的。接近n但是不是等于n，等于n那就是数据本身就是完全有序的。while条件一次都没有满足，while循环体里面的代码，一次都没有走。
            // j>=0很好理解。因为数组的下标不可能为负数。
            // i的值集是[1,2,3,4]
            // 与之对应的j的值集是：
            // 1 : [0]
            // 2 : [1,0]
            // 3 : [2,1,0]
            // 4 : [3,2,1,0]
            // 当array[j]比array[i]大的时候，
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j]; // 那么，当前的array[j]就往后挪动一个位置。那原先array[j + 1]位置上的值不是被覆盖了，于是就丢失了吗。不会，你可以把原来位置要么就想象成空的位置。要么基于代码理解为它保存在key变量里面(int key = array[i];最开始把i位置拿出来保存在key变量里面，你可以结合图形现象它是被抽出来的。或者纯粹就是放在key这个缓存变量里面备份确保不会丢失。)
                j--; // 因为还没有找到目标位置嘛，所以，j还得递减继续往后移动。
            }
            // 当不满足while的条件的时候，其实就是，当前的array[i](int key = array[i])找到了合适的插入位置了,那么就插入到当前的j位置的右边那个位置(注意，是右边，不是左边)。
            array[j + 1] = key;
        }
    }

    // 打印数组方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}




// 后记：
// 冒泡排序、选择排序，虽然有所不同，但是，它们大体上的思路，都是遍历剩下的无序的部分的数组，寻找最值(依靠内层for)，然后依次按顺序摆放到有序区。

// 插入排序的思想则与上面两种完全不一样。它是遍历剩下的无序的部分的数组(依靠外层for)，不寻找最值，直接拿当前元素，在有序区中合适的中间某地带插入(依靠内层while)。

